{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Two Strings to Make Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkPalindromeFormation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割两个字符串得到回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>a</code> 和&nbsp;<code>b</code>&nbsp;，它们长度相同。请你选择一个下标，将两个字符串都在&nbsp;<strong>相同的下标 </strong>分割开。由&nbsp;<code>a</code>&nbsp;可以得到两个字符串：&nbsp;<code>a<sub>prefix</sub></code>&nbsp;和&nbsp;<code>a<sub>suffix</sub></code>&nbsp;，满足&nbsp;<code>a = a<sub>prefix</sub> + a<sub>suffix</sub></code><sub>&nbsp;</sub>，同理，由&nbsp;<code>b</code> 可以得到两个字符串&nbsp;<code>b<sub>prefix</sub></code> 和&nbsp;<code>b<sub>suffix</sub></code>&nbsp;，满足&nbsp;<code>b = b<sub>prefix</sub> + b<sub>suffix</sub></code>&nbsp;。请你判断&nbsp;<code>a<sub>prefix</sub> + b<sub>suffix</sub></code> 或者&nbsp;<code>b<sub>prefix</sub> + a<sub>suffix</sub></code>&nbsp;能否构成回文串。</p>\n",
    "\n",
    "<p>当你将一个字符串&nbsp;<code>s</code>&nbsp;分割成&nbsp;<code>s<sub>prefix</sub></code> 和&nbsp;<code>s<sub>suffix</sub></code>&nbsp;时，&nbsp;<code>s<sub>suffix</sub></code> 或者&nbsp;<code>s<sub>prefix</sub></code> 可以为空。比方说，&nbsp;<code>s = \"abc\"</code>&nbsp;那么&nbsp;<code>\"\" + \"abc\"</code>&nbsp;，&nbsp;<code>\"a\" + \"bc\"&nbsp;</code>，&nbsp;<code>\"ab\" + \"c\"</code>&nbsp;和&nbsp;<code>\"abc\" + \"\"</code>&nbsp;都是合法分割。</p>\n",
    "\n",
    "<p>如果 <strong>能构成回文字符串</strong> ，那么请返回&nbsp;<code>true</code>，否则返回<em>&nbsp;</em><code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意</strong>，&nbsp;<code>x + y</code>&nbsp;表示连接字符串&nbsp;<code>x</code> 和&nbsp;<code>y</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>a = \"x\", b = \"y\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：\n",
    "a<sub>prefix</sub> = \"\", a<sub>suffix</sub> = \"x\"\n",
    "b<sub>prefix</sub> = \"\", b<sub>suffix</sub> = \"y\"\n",
    "那么 a<sub>prefix</sub> + b<sub>suffix</sub> = \"\" + \"y\" = \"y\" 是回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = \"abdef\", b = \"fecab\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>a = \"ulacfd\", b = \"jizalu\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>在下标为 3 处分割：\n",
    "a<sub>prefix</sub> = \"ula\", a<sub>suffix</sub> = \"cfd\"\n",
    "b<sub>prefix</sub> = \"jiz\", b<sub>suffix</sub> = \"alu\"\n",
    "那么 a<sub>prefix</sub> + b<sub>suffix</sub> = \"ula\" + \"alu\" = \"ulaalu\" 是回文串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>a.length == b.length</code></li>\n",
    "\t<li><code>a</code> 和&nbsp;<code>b</code>&nbsp;都只包含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-two-strings-to-make-palindrome](https://leetcode.cn/problems/split-two-strings-to-make-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-two-strings-to-make-palindrome](https://leetcode.cn/problems/split-two-strings-to-make-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"x\"\\n\"y\"', '\"xbdef\"\\n\"xecab\"', '\"ulacfd\"\\n\"jizalu\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # 如果a_prefix + b_prefix可以构成回文串则返回True， 否则返回False\n",
    "        def check(a: str, b:str) -> bool:\n",
    "            i, j = 0, len(a) - 1 # 相向双指针\n",
    "            while i < j and a[i] == b[j]: # 前后缀尽量匹配\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i: j + 1], b[i: j + 1] # 中间剩余部分\n",
    "            return s == s[::-1] or t == t[::-1] # 判断是否为回文串\n",
    "        return check(a, b) or check(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # n = len(a)\n",
    "        # if n == 1:\n",
    "        #     return True\n",
    "        # def func(a,b):\n",
    "        #     n = len(a)\n",
    "        #     for i in range(n//2):\n",
    "        #         if a[i] != b[n - 1 - i]:\n",
    "        #             if a[i:n-i] == a[i:n-i][::-1]:\n",
    "        #                 return True\n",
    "        #             elif b[i:n - i] == b[i:n - i][::-1]:\n",
    "        #                 return True\n",
    "        #             return False\n",
    "        #     return True\n",
    "        # return func(a,b) or func(b,a)\n",
    "\n",
    "        n = len(a)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        \n",
    "        def func(a, b):\n",
    "            for i in range(n // 2):\n",
    "                if a[i] != b[n - 1 - i]:\n",
    "                    if a[i:n - i] == a[i:n - i][::-1] or b[i:n - i] == b[i:n - i][::-1]:\n",
    "                        return True\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        return func(a, b) or func(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # 如果 a_prefix + b_suffix 可以构成回文串则返回 True，否则返回 False\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            i, j = 0, len(a) - 1  # 相向双指针\n",
    "            while i < j and a[i] == b[j]:  # 前后缀尽量匹配\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i: j + 1], b[i: j + 1]  # 中间剩余部分\n",
    "            return s == s[::-1] or t == t[::-1]  # 判断是否为回文串\n",
    "        return check(a, b) or check(b, a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def is_palindrome(s, i, j):\n",
    "            while i<=j and s[i]==s[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return i>=j\n",
    "        \n",
    "        def check(a, b):\n",
    "            i, j = 0, len(a)-1\n",
    "            while i<=j and a[i]==b[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return is_palindrome(a, i, j) or is_palindrome(b, i, j)\n",
    "        \n",
    "        return check(a, b) or check(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # 暴力解法\n",
    "        n = len(b)\n",
    "\n",
    "        def is_hui(s):\n",
    "            p1 = 0\n",
    "            p2 = len(s) - 1\n",
    "            while p1 < p2:\n",
    "                if s[p1] != s[p2]:\n",
    "                    return False\n",
    "                p1 += 1\n",
    "                p2 -= 1\n",
    "            return True\n",
    "\n",
    "        if is_hui(a) or is_hui(b):\n",
    "            return True\n",
    "        \n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if a[p1] != b[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "        if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "            return True\n",
    "\n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if b[p1] != a[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "\n",
    "        if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_palindrome(self, s: str) -> bool:\n",
    "        if len(s) <= 1:\n",
    "            return True\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        if self.is_palindrome(a) or self.is_palindrome(b):\n",
    "            return True\n",
    "\n",
    "        n = len(a)\n",
    "\n",
    "        i, j = 0, n - 1\n",
    "        while i < j and a[i] == b[j]:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        # print(i, j)\n",
    "        res = i >= j or self.is_palindrome(a[i:j + 1]) or self.is_palindrome(b[i:j + 1])\n",
    "        if res:\n",
    "            return True\n",
    "\n",
    "        i, j = 0, n - 1\n",
    "        while i < j and b[i] == a[j]:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        # print(i, j)\n",
    "        return i >= j or self.is_palindrome(a[i:j + 1]) or self.is_palindrome(b[i:j + 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            i, j = 0, len(a) - 1  # 相向双指针\n",
    "            while i < j and a[i] == b[j]:  # 前后缀尽量匹配\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i: j + 1], b[i: j + 1]  # 中间剩余部分\n",
    "            return s == s[::-1] or t == t[::-1]  # 判断是否为回文串\n",
    "        return check(a, b) or check(b, a)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # 判断x,y进行拆分是否存在合法分割\n",
    "        def check(x,y):\n",
    "            l = 0\n",
    "            r = len(x)-1\n",
    "            while l < r and x[l] == y[r]:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            a_remain,b_remain = x[l:r+1],y[l:r+1]\n",
    "            return a_remain == a_remain[::-1] or b_remain == b_remain[::-1]\n",
    "        return check(a,b) or check(b,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def IsPli(s: str) -> bool:\n",
    "    n = len(s)\n",
    "    i, j = 0, n - 1\n",
    "    while i <= j and s[i] == s[j]:\n",
    "        i += 1\n",
    "        j -= 1\n",
    "    return bool(i >= j)\n",
    "\n",
    "def check(a: str, b: str, i: int) -> bool:\n",
    "    return IsPli(a[:i] + b[i:]) | IsPli(b[:i] + a[i:])\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        i = j = 0\n",
    "        while i < n and b[i] == a[n - 1 - i]:\n",
    "            i += 1\n",
    "        while j < n and a[j] == b[n - 1 - j]:\n",
    "            j += 1\n",
    "        if i == n or j == n:\n",
    "            return True\n",
    "        return check(a, b, i) | check(a, b, n - i) | check(a, b, j) | check(a, b, n - j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n=len(a)\n",
    "        p=n//2+1               \n",
    "        x=y=p\n",
    "        for i in range((n-1)//2,-1,-1):\n",
    "            if a[i]!=a[n-i-1]:\n",
    "                x=i\n",
    "            if b[i]!=b[n-i-1]:\n",
    "                y=i\n",
    "            if x<p and y<p:\n",
    "                break\n",
    "        if x==p and y==p:\n",
    "            return True\n",
    "        l=n\n",
    "        z=min(x,y)\n",
    "        for i in range(z+1):\n",
    "            if a[i]==b[n-i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                l=i\n",
    "                break\n",
    "        if l==n:\n",
    "            return True\n",
    "        l=n\n",
    "        for i in range(z+1):\n",
    "            if b[i]==a[n-i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                l=i\n",
    "                break\n",
    "        if l==n:\n",
    "            return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        if a == a[::-1] or b == b[::-1]: return True\n",
    "        l = 0\n",
    "        r = len(a) - 1\n",
    "        while l < r:\n",
    "            if a[l] != b[r]:\n",
    "                break\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if l >= r or a[l:r+1] == a[r:l-1:-1] or b[l:r+1] == b[r:l-1:-1]: return True\n",
    "        l = 0\n",
    "        r = len(a) - 1\n",
    "        while l < r:\n",
    "            if b[l] != a[r]:\n",
    "                break\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if l >= r or a[l:r+1] == a[r:l-1:-1] or b[l:r+1] == b[r:l-1:-1]: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "\n",
    "        def check_self(a: str, left: int, right: int) -> bool:\n",
    "            while left < right and a[left] == a[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return left >= right\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            left, right = 0, n - 1\n",
    "            while left < right and a[left] == b[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if left >= right:\n",
    "                return True\n",
    "            return check_self(a, left, right) or check_self(b, left, right)\n",
    "\n",
    "        return check(a, b) or check(b, a)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        return self.checkConcatenation(a, b) or self.checkConcatenation(b, a)\n",
    "    def checkSelfPalindrome(self, a, left, right):\n",
    "        while left < right and a[left] == a[right]:\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return left >= right \n",
    "    \n",
    "    def checkConcatenation(self, a, b):\n",
    "        n = len(a)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left < right and a[left] == b[right]:\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        if left >= right:\n",
    "            return True\n",
    "        return self.checkSelfPalindrome(a, left, right) or self.checkSelfPalindrome(b, left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def ab(one, two):\n",
    "            lift, right = 0, len(a)-1\n",
    "            while lift <= right and one[lift] == two[right]:\n",
    "                lift += 1\n",
    "                right -= 1\n",
    "            if lift >= right:\n",
    "                return True\n",
    "            return one[lift:right+1] == one[lift:right+1][::-1] or two[lift:right+1] == two[lift:right+1][::-1]\n",
    "        return ab(a,b) or ab(b,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b) or fun(b,a):\n",
    "            # return True\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        length = len(a)\n",
    "        def isStr(str):\n",
    "            if str[::-1] == str:\n",
    "                return True\n",
    "            else: return False\n",
    "        if isStr(a) or isStr(b):\n",
    "            return True\n",
    "        t = b[::-1]\n",
    "        if a == t: return True\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while a[p] == t[p] or a[length - q - 1] == t[length - q - 1]:\n",
    "            p += 1 if a[p] == t[p] else 0\n",
    "            q += 1 if a[length - q - 1] == t[length - q - 1] else 0\n",
    "        # print(isStr(b[p : length - p]), a[q:length - q])\n",
    "        if (isStr(b[p : length - p]) or isStr(a[q:length - q])) or (isStr(a[p : length - p]) or isStr(b[q:length - q])) : return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        i = 0\n",
    "        while i < n /2 and a[i] == b[n-i-1]:\n",
    "            i += 1\n",
    "        j = 0\n",
    "        while j < n/2 and b[j] == a[n-1-j]:\n",
    "            j += 1\n",
    "        anchor = max(i,j)\n",
    "        l = anchor\n",
    "        r = n - 1 - anchor\n",
    "        while r - l >= 1 and a[l] == a[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if r - l < 1:\n",
    "            return True\n",
    "        l = anchor\n",
    "        r = n - 1 - anchor\n",
    "        while r - l >= 1 and b[l] == b[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if r - l < 1:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        if a == a[::-1] or b == b[::-1]:\n",
    "            return True\n",
    "        n = len(a)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            if a[i] != b[j]:\n",
    "                break\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i - 1 >= 0 and (b[i:j + 1] == b[i:j + 1][::-1] or a[i:j + 1] == a[i:j + 1][::-1]):\n",
    "            return True\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            if b[i] != a[j]:\n",
    "                break\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i - 1 >= 0 and (a[i:j + 1] == a[i:j + 1][::-1] or b[i:j + 1] == b[i:j + 1][::-1]):\n",
    "            return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        return self.checkConcatenation(a, b) or self.checkConcatenation(b, a)\n",
    "    \n",
    "    def checkConcatenation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        left, right = 0, n - 1\n",
    "        while left < right and a[left] == b[right]:\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        if left >= right:\n",
    "            return True\n",
    "        return self.checkSelfPalindrome(a, left, right) or self.checkSelfPalindrome(b, left, right)\n",
    "\n",
    "    def checkSelfPalindrome(self, a: str, left: int, right: int) -> bool:\n",
    "        while left < right and a[left] == a[right]:\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return left >= right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        def check1(s):\n",
    "            left, right = 0, len(s)-1\n",
    "            while(left < right):\n",
    "                if(s[left] != s[right]):\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        if(check1(a) or check1(b)):\n",
    "            return True\n",
    "\n",
    "        def check2(a, b):\n",
    "            left, right = 0, len(a)-1\n",
    "            while(left < right and a[left] == b[right]):\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if(left >= right):\n",
    "                return True\n",
    "            return check1(a[left:right+1]) or check1(b[left:right+1])\n",
    "        if(check2(a,b) or check2(b,a)):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "\n",
    "        def check(a, b):\n",
    "            i, j = 0, len(a) - 1\n",
    "            while i < j and a[i] == b[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i: j+1], b[i:j+1]\n",
    "            return s == s[::-1] or t == t[::-1]\n",
    "        \n",
    "        return check(a, b) or check(b, a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        def func(a,b):\n",
    "            n = len(a)\n",
    "            for i in range(n//2):\n",
    "                if a[i] != b[n - 1 - i]:\n",
    "                    if a[i:n-i] == a[i:n-i][::-1]:\n",
    "                        return True\n",
    "                    elif b[i:n - i] == b[i:n - i][::-1]:\n",
    "                        return True\n",
    "                    return False\n",
    "            return True\n",
    "        return func(a,b) or func(b,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        # 双指针\n",
    "        def check(a,b):\n",
    "            left,right = 0,n-1# 相向双指针\n",
    "            while left<right and a[left] == b[right] :# 前后缀尽量匹配\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            s, t = a[left: right+1], b[left: right+1]  # 中间剩余部分\n",
    "            return s == s[::-1] or t == t[::-1]# 判断中间是否为回文串\n",
    "        return check(a, b) or check(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        def check1(s):\n",
    "            left, right = 0, len(s)-1\n",
    "            while(left < right):\n",
    "                if(s[left] != s[right]):\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        if(check1(a) or check1(b)):\n",
    "            return True\n",
    "\n",
    "        def check2(a, b):\n",
    "            left, right = 0, len(a)-1\n",
    "            while(left < right and a[left] == b[right]):\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if(left >= right):\n",
    "                return True\n",
    "            return check1(a[left:right+1]) or check1(b[left:right+1])\n",
    "        if(check2(a,b) or check2(b,a)):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n=len(a)\n",
    "        #a在前\n",
    "        xiangtong=0\n",
    "        while xiangtong<n and a[xiangtong]==b[-xiangtong-1]:\n",
    "            xiangtong+=1\n",
    "        if xiangtong>=n//2:return True\n",
    "        if a[xiangtong:n-xiangtong]==a[xiangtong:n-xiangtong][::-1] or b[xiangtong:n-xiangtong]==b[xiangtong:n-xiangtong][::-1]:\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        #b在前\n",
    "        a,b=b,a\n",
    "        xiangtong=0\n",
    "        while xiangtong<n and a[xiangtong]==b[-xiangtong-1]:\n",
    "            xiangtong+=1\n",
    "        if xiangtong>=n//2:return True\n",
    "        if a[xiangtong:n-xiangtong]==a[xiangtong:n-xiangtong][::-1] or b[xiangtong:n-xiangtong]==b[xiangtong:n-xiangtong][::-1]:\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def judge(a:str)->bool:\n",
    "            left,right = 0,len(a)-1\n",
    "            while left<right:\n",
    "                if a[left]!=a[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "        def check(a:str,b:str)->bool:\n",
    "            left,right=0,len(a)-1\n",
    "            while left<right:\n",
    "                if a[left]!=b[right]:\n",
    "                    break\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return judge(a[left:right+1]) or judge(b[left:right+1])\n",
    "                \n",
    "        return check(a,b) or check(b,a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        \n",
    "        def check(a, b):\n",
    "            n = len(a)\n",
    "            i, j = 0, n-1\n",
    "            while i < j and a[i] == b[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i:j+1], b[i:j+1]\n",
    "            return s == s[::-1] or t == t[::-1]\n",
    "        \n",
    "        return check(a, b) or check(b, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        length = len(a)\n",
    "        def isStr(str):\n",
    "            if str[::-1] == str:\n",
    "                return True\n",
    "            else: return False\n",
    "        if isStr(a) or isStr(b):\n",
    "            return True\n",
    "        t = b[::-1]\n",
    "        if a == t: return True\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while a[p] == t[p] or a[length - q - 1] == t[length - q - 1]:\n",
    "            p += 1 if a[p] == t[p] else 0\n",
    "            q += 1 if a[length - q - 1] == t[length - q - 1] else 0\n",
    "        if (isStr(b[p : length - p]) or isStr(a[q:length - q])) or (isStr(a[p : length - p]) or isStr(b[q:length - q])) : return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "\n",
    "        def check(a, b):\n",
    "            i, j = 0, len(a) -1\n",
    "            while i < j and a[i] == b[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s, t = a[i:j+1], b[i:j+1]\n",
    "            return s == s[::-1] or t == t[::-1]\n",
    "        \n",
    "        return check(a, b) or check(b, a)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # n = len(a)\n",
    "        # dp1, dp2 = [[True]*n for _ in range(n)], [[True]*n for _ in range(n)]\n",
    "        # for i in range(n-2, -1, -1):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         dp1[i][j] = dp1[i+1][j-1] and a[i] == a[j]\n",
    "        #         dp2[i][j] = dp2[i+1][j-1] and b[i] == b[j]\n",
    "        \n",
    "        def isOK(s, i, j):\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "        \n",
    "        def check(a, b):\n",
    "            n = len(a)\n",
    "            i, j = 0, n-1\n",
    "            while i < j:\n",
    "                if a[i] != b[j]:\n",
    "                    break\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return isOK(a, i, j) or isOK(b, i, j)\n",
    "        \n",
    "        return check(a,b) or check(b,a)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        def check1(s):\n",
    "            left, right = 0, len(s)-1\n",
    "            while(left < right):\n",
    "                if(s[left] != s[right]):\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        if(check1(a) or check1(b)):\n",
    "            return True\n",
    "\n",
    "        def check2(a, b):\n",
    "            left, right = 0, len(a)-1\n",
    "            while(left < right and a[left] == b[right]):\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if(left >= right):\n",
    "                return True\n",
    "            return check1(a[left:right+1]) or check1(b[left:right+1])\n",
    "        if(check2(a,b) or check2(b,a)):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def check1(a: str, b: str) -> bool:\n",
    "            i, j = 0, len(b) - 1\n",
    "            while i < j and a[i] == b[j]:\n",
    "                i, j = i + 1, j - 1\n",
    "            return i >= j or check2(a, i, j) or check2(b, i, j)\n",
    "\n",
    "        def check2(a: str, i: int, j: int) -> bool:\n",
    "            return a[i: j + 1] == a[i: j + 1][::-1]\n",
    "\n",
    "        return check1(a, b) or check1(b, a)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def IsPli(s: str) -> bool:\n",
    "    n = len(s)\n",
    "    i, j = 0, n - 1\n",
    "    while i <= j and s[i] == s[j]:\n",
    "        i += 1\n",
    "        j -= 1\n",
    "    return bool(i >= j)\n",
    "\n",
    "def check(a: str, b: str, i: int) -> bool:\n",
    "    return IsPli(a[:i] + b[i:]) | IsPli(b[:i] + a[i:])\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        if IsPli(a) | IsPli(b):\n",
    "            return True\n",
    "        n = len(a)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        i = j = 0\n",
    "        while i < n and b[i] == a[n - 1 - i]:\n",
    "            i += 1\n",
    "        while j < n and a[j] == b[n - 1 - j]:\n",
    "            j += 1\n",
    "        return bool(i == n or j == n) | check(a, b, i) | check(a, b, n - i) | check(a, b, j) | check(a, b, n - j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def fun(s,left,right):\n",
    "            while left < right and s[left] == s[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if left >= right:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        n = len(b)\n",
    "        l,r = 0,n-1\n",
    "        f = [[],[]]\n",
    "        while l < r and (len(f[0]) == 0 or len(f[1]) == 0):\n",
    "            if a[l] != b[r] and len(f[0]) == 0:\n",
    "                f[0].append(l)\n",
    "                f[0].append(r)\n",
    "            if b[l] != a[r]  and len(f[1]) == 0:\n",
    "                f[1].append(l)\n",
    "                f[1].append(r)\n",
    "            r -= 1\n",
    "            l += 1\n",
    "        if len(f[0]) + len(f[1]) < 4:\n",
    "            return True\n",
    "        return fun(a,f[0][0],f[0][1]) or fun(b,f[1][0],f[1][1]) or fun(b,f[0][0],f[0][1]) or fun(a,f[1][0],f[1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n=len(a)\n",
    "        k=-1\n",
    "        x=0\n",
    "        y=0\n",
    "        for i in range(n-1):\n",
    "            if a[i]==b[n-1-i]:\n",
    "                k=i\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        str1=a[k+1:n-1-k:1]\n",
    "        str2=b[k+1:n-k-1:1]\n",
    "        if n==1 or k>=int(n/2)-1 or str1==str1[::-1] or str2==str2[::-1]:\n",
    "            x=1\n",
    "        for i in range(n-1):\n",
    "            if b[i]==a[n-1-i]:\n",
    "                k=i\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        str1=a[k+1:n-1-k:1]\n",
    "        str2=b[k+1:n-k-1:1]\n",
    "        if n==1 or k>=int(n/2)-1 or str1==str1[::-1] or str2==str2[::-1]:\n",
    "            y=1\n",
    "        if x+y>0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "             \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        l, r = 0, n-1\n",
    "        while (l < r and a[l] == b[r]) :\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        sl, sr = l, r\n",
    "        while (sl < sr and a[sl] == a[sr]) :\n",
    "            sl += 1\n",
    "            sr -= 1\n",
    "        if sl >= sr :\n",
    "            return True\n",
    "        sl, sr = l, r\n",
    "        while (sl < sr and b[sl] == b[sr]) :\n",
    "            sl += 1\n",
    "            sr -= 1\n",
    "        if sl >= sr :\n",
    "            return True\n",
    "\n",
    "        l, r = 0, n-1\n",
    "        while (l < r and b[l] == a[r]) :\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        sl, sr = l, r\n",
    "        while (sl < sr and a[sl] == a[sr]) :\n",
    "            sl += 1\n",
    "            sr -= 1\n",
    "        if sl >= sr :\n",
    "            return True\n",
    "        sl, sr = l, r\n",
    "        while (sl < sr and b[sl] == b[sr]) :\n",
    "            sl += 1\n",
    "            sr -= 1\n",
    "        if sl >= sr :\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # ~~~\n",
    "        n = len(b)\n",
    "\n",
    "        def is_hui(s):\n",
    "            p1 = 0\n",
    "            p2 = len(s) - 1\n",
    "            while p1 < p2:\n",
    "                if s[p1] != s[p2]:\n",
    "                    return False\n",
    "                p1 += 1\n",
    "                p2 -= 1\n",
    "            return True\n",
    "               \n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if a[p1] != b[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "        if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "            return True\n",
    "\n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if b[p1] != a[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "        if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def check(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while i < j and a[i] == b[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s,t = a[i:j+1],b[i:j+1]\n",
    "            return s == s[::-1] or t == t[::-1]\n",
    "        return check(a,b) or check(b,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        # 暴力解法\n",
    "        n = len(b)\n",
    "\n",
    "        def is_hui(s):\n",
    "            p1 = 0\n",
    "            p2 = len(s) - 1\n",
    "            while p1 < p2:\n",
    "                if s[p1] != s[p2]:\n",
    "                    return False\n",
    "                p1 += 1\n",
    "                p2 -= 1\n",
    "            return True\n",
    "\n",
    "        if is_hui(a) or is_hui(b):\n",
    "            return True\n",
    "        \n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if a[p1] != b[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "        if p1 < p2:\n",
    "            if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "                return True\n",
    "        else:\n",
    "            return True\n",
    "        \n",
    "        p1, p2 = 0, n-1\n",
    "        while p1 < p2:\n",
    "            if b[p1] != a[p2]:\n",
    "                break\n",
    "            p1 += 1\n",
    "            p2 -= 1\n",
    "\n",
    "        if p1 < p2:\n",
    "            if is_hui(a[p1:p2+1]) or is_hui(b[p1:p2+1]):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def judge(a:str)->bool:\n",
    "            left,right = 0,len(a)-1\n",
    "            while left<right:\n",
    "                if a[left]!=a[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "        def check(a:str,b:str)->bool:\n",
    "            left,right=0,len(a)-1\n",
    "            while left<right:\n",
    "                if a[left]!=b[right]:\n",
    "                    break\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return judge(a[left:right+1]) or judge(b[left:right+1])\n",
    "                \n",
    "        return check(a,b) or check(b,a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        def f(a,b):\n",
    "            i,j=0,len(b)-1\n",
    "            while i<=j and a[i]==b[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if j<i: return True\n",
    "            return a[i:j+1]==a[i:j+1][::-1] or b[i:j+1]==b[i:j+1][::-1]\n",
    "        return f(a,b) or f(b,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        n = len(a)\n",
    "        if n==1:\n",
    "            return True\n",
    "        if n % 2:\n",
    "            la,ra= n//2,n//2\n",
    "            lb,rb= n//2,n//2\n",
    "        else:\n",
    "            la,ra= n//2,n//2-1\n",
    "            lb,rb= n//2,n//2-1\n",
    "        def check(s, l,r):\n",
    "            while l-1>=0 and r+1<n and s[l-1] == s[r+1]:\n",
    "                l-=1\n",
    "                r+=1\n",
    "            return l,r    \n",
    "        la,ra = check(a,la,ra)\n",
    "        lb,rb = check(b,lb,rb)\n",
    "        if a[:la] == b[-la:][::-1] or b[:lb] == a[-lb:][::-1]:\n",
    "            return True\n",
    "        if b[:la] == a[-la:][::-1] or a[:lb] == b[-lb:][::-1]:\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        \n",
    "        # 辅助函数：检查字符串是否是回文\n",
    "        def is_palindrome(s):\n",
    "            return s == s[::-1]\n",
    "        \n",
    "        # 辅助函数：检查两个字符串组合是否可以形成回文\n",
    "        def check(s1, s2):\n",
    "            i, j = 0, len(s2) - 1\n",
    "            while i < j and s1[i] == s2[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return is_palindrome(s1[i:j+1]) or is_palindrome(s2[i:j+1])\n",
    "        \n",
    "        # 检查两种组合情况\n",
    "        return check(a, b) or check(b, a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPalindromeFormation(self, a, b):\n",
    "        def fun(a,b):\n",
    "            i,j = 0,len(a)-1\n",
    "            while(i<j and a[i]==b[j]):\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if(i>=j):\n",
    "                #超过中间位置直接为回文\n",
    "                return True\n",
    "           #相同位置结束，判断i或j进行分割是不是回文\n",
    "            res1=a[i:j+1]\n",
    "            res2=b[i:j+1]\n",
    "            if(res1==res1[::-1] or res2==res2[::-1]):\n",
    "                return True \n",
    "        if fun(a,b):\n",
    "            return True\n",
    "        if fun(b,a):\n",
    "            return True\n",
    "        if(a==a[::-1] or b==b[::-1]):\n",
    "            #a or b 是回文\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPalindromeFormation(self, a: str, b: str) -> bool:\n",
    "        for i in range(2):\n",
    "            a = ''.join(reversed(a))\n",
    "            b = ''.join(reversed(b))\n",
    "            left = 0\n",
    "            right = len(b)-1\n",
    "            while left<len(a) and right >=0 and a[left] == b[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            if left >= right:\n",
    "                return True\n",
    "            else:\n",
    "                if ''.join(reversed(a[left:right+1]))==a[left:right+1] or ''.join(reversed(b[left:right+1]))==b[left:right+1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
